/**
 * @Question.Title: 单词拆分 II
 * @Question.No: 140
 * @Author: DQ
 * @Date: 2021-04-22 16:07:41
 * @Description: 
 */
//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的
//句子。 
//
// 说明： 
//
// 
// 分隔时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入:
//s = "catsanddog"
//wordDict = ["cat", "cats", "and", "sand", "dog"]
//输出:
//[
//  "cats and dog",
//  "cat sand dog"
//]
// 
//
// 示例 2： 
//
// 输入:
//s = "pineapplepenapple"
//wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
//输出:
//[
//  "pine apple pen apple",
//  "pineapple pen apple",
//  "pine applepen apple"
//]
//解释: 注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入:
//s = "catsandog"
//wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出:
//[]
// 
// Related Topics 动态规划 回溯算法 
// 👍 444 👎 0

package dq.leetcode.editor.cn;

import java.util.*;

public class WordBreakIi {
    public static void main(String[] args) {
        Solution solution = new WordBreakIi().new Solution();
        String s = "catsanddog";
        String[] wordDictString = new String[]{"cats", "dog", "sand", "and", "cat"};
        List<String> wordDict = Arrays.asList(wordDictString);
        List<String> res = solution.wordBreak(s, wordDict);
        res.forEach(System.out::println);
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {

        return wordBreakWithDfs(s, wordDict);
    }
    public List<String> wordBreakWithDfs(String s, List<String> wordDict) {
        //词典
        Set<String> dict = new HashSet<>(wordDict);
        List<String> res = new ArrayList<>();
        int[] dp = new int[s.length()];
        dfs(s, 0, dict, dp, "", res);
        return res;
    }
    private boolean dfs(String s, int i, Set<String> dict,int[] dp, String pre, List<String> res){
        //如果到达最后
        if(i>=s.length()) {
            res.add(pre);
            return true;
        }
        if(dp[i]==-1) {
            return false;
        }
        for(int k = i+1; k <= s.length(); k++){
            String sub = s.substring(i, k);
            if(dict.contains(sub) && dfs(s, k, dict, dp,pre+" "+sub , res)){
                dp[i] = 1;
//                return true;
            }
        }
        dp[i] = -1;
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}